/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/n-queens-ii
   @Language: C++
   @Datetime: 16-02-09 08:18
   */

class Solution {
	bool isValid(vector<int> &board,int row,int col){
		for(int i=0; i<row; ++i)
			if (board[i]==col || board[i]+row-i==col || board[i]-row+i==col)
				return false;
		return true;
	}
	int NQueen(vector<int> &board,int N,int pos){
		if (pos==N) return 1;
		int sum=0;
		for(int i=0; i<N; ++i){
			board[pos]=i;
			if (isValid(board,pos,i))
				sum += NQueen(board,N,pos+1);
		}
		return sum;
	}

public:
	/**
	 * Calculate the total number of distinct N-Queen solutions.
	 * @param n: The number of queens.
	 * @return: The total number of distinct solutions.
	 */
	int totalNQueens(int n) {
		// write your code here
		vector<int> board(n,-1);
		return NQueen(board,n,0);
	}
};
